package cn.edu.ncepu;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class FermatFactorization {

    /**
     * 费马分解算法：将奇数n分解为两个因数p和q（n = p*q）
     * @param n 待分解的奇数（n > 1）
     * @return 长度为2的数组，[p, q] 其中 p = a - b, q = a + b
     */
    private static long[] fermat(long n) {
        // 校验输入：费马分解适用于奇数，且n > 1
        if (n <= 1 || (n & 1) == 0) {
            throw new IllegalArgumentException("费马分解仅适用于大于1的奇数");
        }

        long a = (long) Math.ceil(Math.sqrt(n));
        long b2 = a * a - n;
        long b = Math.round(Math.sqrt(b2));

        // 循环查找满足b² = a² - n的b值
        while (b * b != b2) {
            a++;
            b2 = a * a - n;
            b = Math.round(Math.sqrt(b2));
        }


        return new long[]{a - b, a + b};
    }

    /**
     * 递归式因式分解：结合费马分解和试除法（偶数直接分解）
     * @param n 待分解的正整数
     * @return 因式分解结果列表（升序排列）
     */
    public static List<Long> factorization(long n) {
        // 校验输入合法性
        if (n <= 1) {
            throw new IllegalArgumentException("待分解数必须大于1");
        }

        List<Long> factors = new LinkedList<>();
        Deque<Long> stack = new LinkedList<>();
        stack.push(n); // 初始化栈，压入待分解数

        while (!stack.isEmpty()) {
            long x = stack.pop();

            // 处理x=2的特殊情况
            if (x == 2) {
                factors.add(x);
                continue;
            }

            long[] pq;
            // 奇数用费马分解，偶数分解为2和x/2
            if ((x & 1) == 1) {
                pq = fermat(x);
            } else {
                pq = new long[]{2, x / 2};
            }

            long p = pq[0];
            long q = pq[1];

            // 如果p=1，说明q是质数，加入因子列表
            if (p == 1) {
                factors.add(q);
            } else {
                // 否则继续分解p和q，压入栈
                stack.push(p);
                stack.push(q);
            }
        }

        return factors;
    }

    public static void main(String[] args) {
        // 测试案例：分解200，与Python版本一致
        List<Long> result = factorization(200);
        System.out.println(result); // 输出 [2, 2, 2, 5, 5]
    }
}